#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "UBigNumber.h"


struct UBigNumber InputUBN(char * s)
{
    struct UBigNumber result;
    _InitUBN(&result);
    for (int i = 0; i < strlen(s); i++)
        _AppendDigit(&result, s[i] - '0');
    _Normalize(&result);
    return result;
}

void PrintUBN(struct UBigNumber ubn)
{
    assert(ubn.digitCount > 0 && ubn.pHead->next != NULL);
    struct Node * la = ubn.pHead->next;
    while(la)
    {
        printf("%d", la->digit);
        la = la -> next;
    }
}

struct UBigNumber AddUBN(struct UBigNumber * pA, struct UBigNumber * pB)
{
    struct UBigNumber result, * pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;
    struct Node * p1, * p2;
    p1 = pA->pTail;
    p2 = pB->pTail;
    while (p1 != pA->pHead && p2 != pB->pHead)
    {
        int digit = p1->digit + p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }
    while (p1 != pA->pHead)
    {
        int digit = p1->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    while (p2 != pB->pHead)
    {
        int digit = p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p2 = p2->prev;
    }
    if (iCarry != 0)
        _AppendFrontDigit(pResult, iCarry);
    return result;
}

struct UBigNumber SubUBN(struct UBigNumber * pA, struct UBigNumber * pB)
{
    struct UBigNumber result;
    _InitUBN(&result);
    int iCarry = 0; // 借位, 初始 0
    struct Node * p1, *p2;
    p1 = pA->pTail; // 从低位开始处理
    p2 = pB->pTail;
    while (p1 != pA->pHead && p2 != pB->pHead) // 两数相同位处理
    {
        int digit = p1->digit - p2->digit + iCarry;
        iCarry = 0;
        if (digit < 0)
        {
            digit += 10; // 当前结果位
            iCarry = -1; // 新借位
        }
        _AppendFrontDigit(&result, digit); // 添加结果最高位
        p1 = p1->prev; // 准备处理前一位
        p2 = p2->prev;
    }
    assert(p2 == pB->pHead);
    while (p1 != pA->pHead) // 第 1 大数剩余位处理
    {
        int digit = p1->digit + iCarry;
        iCarry = 0;
        if (digit < 0)
        {
            digit += 10; // 当前结果位
            iCarry = -1; // 新借位
        }
        _AppendFrontDigit(&result, digit); // 添加至结果最高位
        p1 = p1->prev; // 准备处理前一位
    }
    assert(iCarry == 0);
    _Normalize(&result);
    return result;
}

struct UBigNumber MultiplyUBN(struct UBigNumber * pA, struct UBigNumber * pB)
{
    // 递归中止条件
    if (pB->digitCount == 1)
        return _MultiplyDigit(pA, pB->pTail->digit);
    else if (pA->digitCount == 1)
        return _MultiplyDigit(pB, pA->pTail->digit);

    // 计算拆分长度
    int m = pA->digitCount;
    int n = pB->digitCount;

    int h = (m>n? m : n) / 2;

    /* 拆分为a, b, c, d */
    struct UBigNumber a, b, c, d;

    a = _FetchSub(pA, 0, m-h); // 高 m-h 位
    b = _FetchSub(pA, m-h, m); // 低 h 位
    c = _FetchSub(pB, 0, n-h); // 高 n-h 位
    d = _FetchSub(pB, n-h, n); // 低 h 位

    // 计算 z2, z0, z1, 此处的乘法使用递归实现
    struct UBigNumber z0, z1, z2;

    z2 = MultiplyUBN(&a, &c); // z2 = a * c
    z0 = MultiplyUBN(&b, &d); // z0 = b * d
    struct UBigNumber t1, t2, t3, t4, t5, result;
    t1 = AddUBN(&a, &b); // t1 = a + b
    t2 = AddUBN(&c, &d); // t2 = c + d
    // 销毁各不再使用的无符号大数
    DestroyUBN(&a);
    DestroyUBN(&b);
    DestroyUBN(&c);
    DestroyUBN(&d);
    t3 = MultiplyUBN(&t1, &t2); // t3 = (a + b) * (c + d)
    t4 = AddUBN(&z0, &z2); // t4 = z0 + z2
    z1 = SubUBN(&t3, &t4); // z1 = (a + b) * (c + d) - z2 - z0

    int i;
    for (i = 0; i < 2 * h; ++i) // z2 *= (10^(2 * h))
        _AppendDigit(&z2, 0);
    for (i = 0; i < h; ++i) // z1 *= (10^h)
        _AppendDigit(&z1, 0);
    t5 = AddUBN(&z2, &z1); // t5 = z2 * 10^2h + z1 * 10^h
    result = AddUBN(&t5, &z0); // result = z2 * 10^2h + z1 * 10^h + z0

    DestroyUBN(&z0);
    DestroyUBN(&z1);
    DestroyUBN(&z2);
    DestroyUBN(&t1);
    DestroyUBN(&t2);
    DestroyUBN(&t3);
    DestroyUBN(&t4);
    DestroyUBN(&t5);
    return result;
}


void DestroyUBN(struct UBigNumber * pUBN)
{
    while (pUBN->pHead != NULL)
    {
        struct Node * p = pUBN->pHead;
        pUBN->pHead = p->next;
        free(p);
    }
}

void _InitUBN(struct UBigNumber * pUBN)
{
    struct Node * p = _NewNode();
    pUBN->pHead = pUBN->pTail = p;
    p->next = p->prev = NULL;
    pUBN->digitCount = 0;

}

void _AppendDigit(struct UBigNumber * pUBN, int digit)
{
    // 原来只有一个高位 0
    if(pUBN->digitCount == 1 && pUBN->pTail->digit == 0)
    {
        pUBN->pTail->digit = digit; // 位数不变, 数值为 0
        return;
    }
    struct Node *p = _NewNode(); // 申请新结点
    p->digit = digit; // 设置结点数值
    p->next = NULL; // 修改双向链表, 将新结点添加到尾部
    p->prev = pUBN->pTail;
    pUBN->pTail->next = p;
    pUBN->pTail = p;
    ++pUBN->digitCount;
}

void _AppendFrontDigit(struct UBigNumber * pUBN, int digit)
{
    struct Node *p = _NewNode(); // 申请新结点
    p->digit = digit; // 设置结点数值
    p->next = pUBN->pHead->next; // 修改双向链表, 将新结点添加在头结点后
    if (p->next != NULL)
        p->next->prev = p;
    p->prev = pUBN->pHead;
    pUBN->pHead->next = p;
    if (pUBN->pTail == pUBN->pHead)
        pUBN->pTail = p; // 当原来只有头结点时, 新结点也是尾结点
    ++pUBN->digitCount; // 修改位数
}

void _Normalize(struct UBigNumber * pUBN)
{
    if (pUBN->digitCount == 0)
        _AppendDigit(pUBN, 0);
    while (pUBN->digitCount > 1 && pUBN->pHead->next->digit == 0)
    {   // 去除高位多余的 0
        struct Node *p;
        p = pUBN->pHead->next; // 待删除结点
        pUBN->pHead->next = p->next; // 正向链表中删除
        p->next->prev = pUBN->pHead; // 反向链表中删除
        free(p); // 释放结点
        --pUBN->digitCount; // 调整位数
    }
}

struct Node * _NewNode()
{
    struct Node * p;
    p = (struct Node *) malloc(sizeof(struct Node));
    if (p == NULL)
    {
        printf("Error: out of memory\n");
        exit(-1);
    }
    return p;
}

struct UBigNumber _MultiplyDigit(struct UBigNumber * pA, int digit2)
{
    struct UBigNumber result;
    _InitUBN(&result);
    if (digit2 == 0)
    {
        _AppendDigit(&result, 0);
        return result;
    }

    int iCarry = 0; // 进位, 初始 0
    struct Node * p1;
    p1 = pA->pTail; // 从低位开始处理
    while(p1 != pA->pHead) // 第 1 大数剩余位处理
    {
        int digit = p1->digit * digit2 + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(&result, digit);
        p1 = p1->prev;
    }
    if (iCarry != 0) // 最后进位处理
        _AppendFrontDigit(&result, iCarry);
    return result;
}

struct UBigNumber _FetchSub(struct UBigNumber *pA, int start, int end)
{
    struct UBigNumber result;
    _InitUBN(&result);
    int i = 0;
    struct Node * p = pA->pHead->next;
    while (i < start && p != NULL)
    {
        p = p->next;
        ++i;
    }
    while (i < end && p != NULL)
    {
        _AppendDigit(&result, p->digit); // 添加在尾部
        p = p->next;
        ++i;
    }
    _Normalize(&result);
    return result;
}